package threeSum;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @Date 2020/03/26
 * @author 王光浩
 * @Thinking 使用HashMap，原理：找出所有不同的数字，然后将该数字的所有可能加入到结果集中，随后移除该数字
 * @         思路讲解：首先我们需要知道我们要找的是一个3个数组成的组合，如果我们使用暴力法，可以使用一个三层循环
 * @         每一层循环代表一个数，所有有满足结果的集合以排序完毕后的方式加入到结果集中，然后在最后使用双层循环遍历
 * @         结果集，找出所有重复的结果，将其删除，这样时间复杂度将会到达O（n^3+n^2）,为了减低时间复杂度，我决定使用
 * @         HashMap来存储数据，这样可以提高数据的读取效率，为了进一步降低时间复杂度，我将所有不相同的数字存储在一个数组
 * @         中，然后遍历这个数组，每一遍历将对应数字，将包含对应数字的所有符合条件的结果加入到结果集中，然后将这个数字清除即可
 * @         这样时间复杂度可以降低到O（n^2）
 */
public class MyMethodTwo {
	public List<List<Integer>> threeSum(int[] nums) {
		HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
		List<List<Integer>> ret=new LinkedList<List<Integer>>();
		//统计数字个数
		for(int tem:nums)
			map.put(tem, map.getOrDefault(tem, 0)+1);
		int[] arr=new int[map.size()];
		//将所有不同的数字加入到一个数组中
		int index=0;
		for(int tem:map.keySet())arr[index++]=tem;
		//遍历数组，每次遍历将对应包含该数字的所有可能加入到结果集中
		for(int i=0;i<arr.length;i++) {
			int key=arr[i];
			int value=map.get(key);
			map.remove(key);
			if(value>=3) {
				if(key==0) {
					add(ret,0,0,0);
				}
			}
			if(value>=2 && key!=0) {
				if(map.containsKey(-2*key)) {
					add(ret,key,key,-2*key);
				}
			}
			Set<Integer> set=new HashSet<Integer>();
			for(Map.Entry<Integer, Integer> entry:map.entrySet()) {
				if(!set.contains(entry.getKey()) && map.containsKey(-key-entry.getKey())) {
					if((-key-entry.getKey())==entry.getKey() && entry.getValue()<2)continue;
					set.add(entry.getKey());
					set.add(-key-entry.getKey());
					add(ret,key,entry.getKey(),-key-entry.getKey());
				}
			}
		}
		return ret;
	}
	//将结果添加到结果集中
	private void add(List<List<Integer>> ret,int first,int second,int third) {
		List<Integer> list=new LinkedList<Integer>();
		list.add(first);
		list.add(second);
		list.add(third);
		ret.add(list);
	}
}
